Practice Problems (Week 8)

These practice problems (unlike the exercises) are not assessed. Use them to test your understanding, to challenge yourself, or whatever floats your boat.

1 The Either monad

The purpose of the Either a monad is similar to the Maybe monad: it provides the ability to represent failing computations in a type-safe way.

…but in the Maybe monad, all failures are represented by Nothing, which seems less than optimally informative. With Either a, successful computations are represented by values of type a wrapped under the Left constructor.

Recall the employee database from Lecture 5:

type ID = Int

data Employee = Employee
  { idNumber   :: ID
  , name       :: String
  , supervisor :: Maybe ID
  } deriving (Show,Eq)

type DB = [Employee]

blandingsDB :: DB
blandingsDB =
  --         id name                 supervisor
  [ Employee 1  "The Empress"      $ Nothing,
    Employee 2  "Lord Emsworth"    $ Just 1,
    Employee 3  "Beach the Butler" $ Just 3,
    Employee 4  "Gloria Salt"      $ Just 5
  ]

lookupID :: Int -> DB -> Maybe Employee
lookupID n [] = Nothing
lookupID n (e:es)
  | idNumber e == n = Just e
  | otherwise       = lookupID n es

supervisorOf :: Int -> DB -> Maybe Employee
supervisorOf id db =
  lookupID id db >>= \e ->
  supervisor e >>= \id' ->
  lookupID id' db >>= \e' -> return e'
{- alternatively in do notation:

supervisorOf :: Int -> DB -> Maybe Employee
supervisorOf id db =
  do
    e <- lookupID id db
    id' <- supervisor e
    e' <- lookupID id' db
    return e'
 -}

Modify this to a function of type Int -> DB -> Either String Employee such that each possible reason for failure gives a different error message wrapped in Left.

You may find this combinator helpful for endowing Maybe computations with error messages:

failWith :: Maybe b -> a -> Either a b
failWith res err = maybe (Left err) Right res

2 The Generator monad

Generator a e r is an abstract representation of a computation as an infinitely branching tree. The computation that may perform observable events of type e, which will yield answers from the environment of type a; the tree-like structure comes about because what the computation does next may depend on a. Terminating computations yield a final return value r.

data Generator a e r = Final r | Next e (a -> Generator a e r)

For example, here's a Generator that represents a computation that receives two numbers, and prints their sum.

sumTwo :: Generator Int String Int
sumTwo =
  Next "getInt" (\x -> Next "getInt" (\y -> Final(x + y)))

Write a sumThree.
Write a sumToTwenty, which will keep doing getInt events until the sum of all thus received numbers is at least 20. (As you might expect, this requires recursion).

Write an appropriate Monad instance for Generator a e. Here's a template with everything except bind:

instance Functor (Generator a e) where
  fmap f (Final x) = Final $ f x
  fmap f (Next y g) = Next y (\x -> fmap f (g x))

instance Applicative (Generator a e) where
  pure = Final
  mf <*> mg = do
    f <- mf
    g <- mg
    return $ f g

instance Monad (Generator a e) where
  return = pure
  f >>= g = undefined -- TODO

Similarly to the state and IO monads, bind acts like sequential composition of computations. The following combinator is useful for doing an event and returning the result:
```
yield :: e -> Generator a e a
yield x = Next x return
```
For example, we can now express sumTwo as follows:
```
sumTwo' :: Generator Int String Int
sumTwö́ =
  do
    x <- yield "getInt"
    y <- yield "getInt"
    return(x + y)
```
or equivalently:
```
sumTwo'' :: Generator Int String Int
sumTwo'' =
yield "getInt" >>= \x ->
yield "getInt" >>= \y ->
return(x + y)
```
(If you are not convinced that these are the same, equational reasoning may help). Similarly rewrite sumToTwenty, but without mentioning Next and Final.
In a certain sense, Generator a e is the most general of all monads, in the sense that given an abstract computation in Generator a e, we can define an interpreter function that translates this into a concrete computation in your favourite monad. This is parameterised on a mapping from events to monad actions.
```
interpret :: Monad m => (e -> m a) -> Generator a e r -> m r
```
Given a correct implementation, the following should be an IO computation that reads two numbers from the command line, and returns their sum:
```
interpret (const $ read <$> getLine) sumTwo
```
Find an x such that
```
interpret x == id
```
Translate this IO computation into generator style, and find a suitable interpreter that lets you recover the original IO computation:
```
-- Read a file name from stdIn, and print the first 10 characters
-- of the file
readAndPrint10 :: IO String
readAndPrint10 = do
  fileName <- getLine
  file <- readFile fileName
  return $ take 10 file
```
Unlike previous examples, this computation requires two distinct monad actions, so the interpreter can no longer be a constant function. Moreover, one of the monad actions takes an argument and the other doesn't. Accounting for that will require a more sophisticated event type than String. Here's my suggestion:
```
data Event = GetLine | ReadFile String deriving (Eq,Show)
```
That was a very roundabout way to write a simple terminal program, so what's the point?

Notice that we can run interpret sumTwo in any monad, not just the IO monad. For example, try this:
```
interpret (const $ [1..5]) sumTwo
```
Thus, Generator can be used to write an abstract monadic computation with abstract monad actions, without committing up-front to which monad the computation should be run in.

This means that IO computations written as generators can be tested without actually performing any IO. To do this, we would interpret them in a different monad. Can you use this idea to write a quickCheck property which tests whether sumTwo is correct, in the sense that it returns the sum of its inputs?

This exercise has been about a simplified presentation of free monads, which will receive no further coverage in this course.